ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Matrix analytic method</title>

</head>

Matrix analytic method

</h1>

</header>

In <a href="Probability_theory" title="Probability theory">probability theory</a>, the matrix analytic method is a technique to compute the stationary <a href="Probability_distribution" title="Probability distribution">probability distribution</a> of a <a href="Markov_chain" title="Markov chain">Markov chain</a> which has a repeating structure (after some point) and a state space which grows unboundedly in no more than one dimension.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a> Such models are often described as <a href="M/G/1_type_Markov_chain" class="mw-redirect" title="M/G/1 type Markov chain">M/G/1 type Markov chains</a> because they can describe transitions in an M/G/1 queue.<a href="#cite_note-meini-3">[3]</a><a href="#cite_note-4">[4]</a> The method is a more complicated version of the <a href="Matrix_geometric_method" title="Matrix geometric method">matrix geometric method</a> and is the classical solution method for M/G/1 chains.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Method_description">Method description</h2></div>

An M/G/1-type stochastic matrix is one of the form<a href="#cite_note-meini-3">[3]</a>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P={\begin{pmatrix}B_{0}&B_{1}&B_{2}&B_{3}&\cdots \\A_{0}&A_{1}&A_{2}&A_{3}&\cdots \\&A_{0}&A_{1}&A_{2}&\cdots \\&&A_{0}&A_{1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}</annotation>

</semantics>

</math><img src="./277402d44d959fd293bc3dd1d31a99f95d39aab5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.171ex; width:33.204ex; height:17.509ex;" alt="{\displaystyle P={\begin{pmatrix}B_{0}&B_{1}&B_{2}&B_{3}&\cdots \\A_{0}&A_{1}&A_{2}&A_{3}&\cdots \\&A_{0}&A_{1}&A_{2}&\cdots \\&&A_{0}&A_{1}&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}" loading="lazy"></dd></dl></dd></dl>

where Bi and Ai are k × k matrices. (Note that unmarked matrix entries represent zeroes.) Such a matrix describes the <a href="Embedded_Markov_chain" class="mw-redirect" title="Embedded Markov chain">embedded Markov chain</a> in an M/G/1 queue.<a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a> If P is <a href="Markov_chain#Reducibility" title="Markov chain">irreducible</a> and <a href="Positive_recurrent" class="mw-redirect" title="Positive recurrent">positive recurrent</a> then the stationary distribution is given by the solution to the equations<a href="#cite_note-meini-3">[3]</a>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1}</annotation>

</semantics>

</math><img src="./a2431e9a84d1c8dc6f1176536e59631557c8252e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:25.299ex; height:2.676ex;" alt="{\displaystyle P\pi =\pi \quad {\text{ and }}\quad \mathbf {e} ^{\text{T}}\pi =1}" loading="lazy"></dd></dl></dd></dl>

where e represents a vector of suitable dimension with all values equal to 1. Matching the structure of P, π is partitioned to π1, π2, π3, …. To compute these probabilities the column stochastic matrix G is computed such that<a href="#cite_note-meini-3">[3]</a>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.}</annotation>

</semantics>

</math><img src="./2487196a5c04b07f0cb870a8e572a726df1aa85c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:14.483ex; height:6.843ex;" alt="{\displaystyle G=\sum _{i=0}^{\infty }G^{i}A_{i}.}" loading="lazy"></dd></dl></dd></dl>

G is called the auxiliary matrix.<a href="#cite_note-8">[8]</a> Matrices are defined<a href="#cite_note-meini-3">[3]</a>

<mtr>

<mtd>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\overline {A}}_{i+1}&=\sum _{j=i+1}^{\infty }G^{j-i-1}A_{j}\\{\overline {B}}_{i}&=\sum _{j=i}^{\infty }G^{j-i}B_{j}\end{aligned}}}</annotation>

</semantics>

</math><img src="./2093341b852e6839eae77b24f96766a59e0ec3a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.671ex; width:22.955ex; height:14.509ex;" alt="{\displaystyle {\begin{aligned}{\overline {A}}_{i+1}&=\sum _{j=i+1}^{\infty }G^{j-i-1}A_{j}\\{\overline {B}}_{i}&=\sum _{j=i}^{\infty }G^{j-i}B_{j}\end{aligned}}}" loading="lazy"></dd></dl></dd></dl>

then π0 is found by solving<a href="#cite_note-meini-3">[3]</a>

<mtr>

<mtd>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

<msup>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\overline {B}}_{0}\pi _{0}&=\pi _{0}\\\quad \left(\mathbf {e} ^{\text{T}}+\mathbf {e} ^{\text{T}}\left(I-\sum _{i=1}^{\infty }{\overline {A}}_{i}\right)^{-1}\sum _{i=1}^{\infty }{\overline {B}}_{i}\right)\pi _{0}&=1\end{aligned}}}</annotation>

</semantics>

</math><img src="./dd23c374fdff8e596808a71a2f549b6522573c2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.338ex; width:46.747ex; height:11.843ex;" alt="{\displaystyle {\begin{aligned}{\overline {B}}_{0}\pi _{0}&=\pi _{0}\\\quad \left(\mathbf {e} ^{\text{T}}+\mathbf {e} ^{\text{T}}\left(I-\sum _{i=1}^{\infty }{\overline {A}}_{i}\right)^{-1}\sum _{i=1}^{\infty }{\overline {B}}_{i}\right)\pi _{0}&=1\end{aligned}}}" loading="lazy"></dd></dl></dd></dl>

and the πi are given by Ramaswami's formula,<a href="#cite_note-meini-3">[3]</a> a numerically stable relationship first published by Vaidyanathan Ramaswami in 1988.<a href="#cite_note-9">[9]</a>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{i}=(I-{\overline {A}}_{1})^{-1}\left[{\overline {B}}_{i+1}\pi _{0}+\sum _{j=1}^{i-1}{\overline {A}}_{i+1-j}\pi _{j}\right],i\geq 1.}</annotation>

</semantics>

</math><img src="./0991a5676c9a24717aacd3ebc56c35add63d201b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:49.208ex; height:7.676ex;" alt="{\displaystyle \pi _{i}=(I-{\overline {A}}_{1})^{-1}\left[{\overline {B}}_{i+1}\pi _{0}+\sum _{j=1}^{i-1}{\overline {A}}_{i+1-j}\pi _{j}\right],i\geq 1.}" loading="lazy"></dd></dl></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Computation_of_G">Computation of G</h2></div>

There are two popular <a href="Iterative_method" title="Iterative method">iterative methods</a> for computing G,<a href="#cite_note-10">[10]</a><a href="#cite_note-11">[11]</a>

<ul><li>functional iterations</li>

<li><a href="Cyclic_reduction" title="Cyclic reduction">cyclic reduction</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Tools">Tools</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cs.wm.edu/MAMSolver/">MAMSolver</a><a href="#cite_note-12">[12]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHarchol-Balter2012" class="citation book cs1"><a href="Mor_Harchol-Balter" title="Mor Harchol-Balter">Harchol-Balter, M.</a> (2012). "Phase-Type Distributions and Matrix-Analytic Methods". Performance Modeling and Design of Computer Systems. pp. 359–379. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9781139226424.028">10.1017/CBO9781139226424.028</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781139226424</bdi>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFNeuts1984" class="citation journal cs1">Neuts, M. F. (1984). "Matrix-analytic methods in queuing theory". European Journal of Operational Research. 15: 2–12. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0377-2217%2884%2990034-1">10.1016/0377-2217(84)90034-1</a>.</cite>

</li>

<li id="cite_note-meini-3">^ <a href="#cite_ref-meini_3-0">a</a> <a href="#cite_ref-meini_3-1">b</a> <a href="#cite_ref-meini_3-2">c</a> <a href="#cite_ref-meini_3-3">d</a> <a href="#cite_ref-meini_3-4">e</a> <a href="#cite_ref-meini_3-5">f</a> <a href="#cite_ref-meini_3-6">g</a> <cite id="CITEREFMeini1997" class="citation journal cs1"><a href="Beatrice_Meini" title="Beatrice Meini">Meini, B.</a> (1997). "An improved FFT-based version of Ramaswami's formula". Communications in Statistics. Stochastic Models. 13 (2): 223–238. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F15326349708807423">10.1080/15326349708807423</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFStathopoulosRiskaHuaSmirni2005" class="citation journal cs1">Stathopoulos, A.; Riska, A.; Hua, Z.; <a href="Evgenia_Smirni" title="Evgenia Smirni">Smirni, E.</a> (2005). "Bridging ETAQA and Ramaswami's formula for the solution of M/G/1-type processes". Performance Evaluation. 62 (1–4): 331–348. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.9473">10.1.1.80.9473</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.peva.2005.07.003">10.1016/j.peva.2005.07.003</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFRiskaSmirni2002" class="citation book cs1">Riska, A.; <a href="Evgenia_Smirni" title="Evgenia Smirni">Smirni, E.</a> (2002). <a rel="nofollow" class="external text" href="http://www.cs.wm.edu/~riska/paper-MG1-tutorial.pdf">"M/G/1-Type Markov Processes: A Tutorial"</a> (PDF). <a rel="nofollow" class="external text" href="https://archive.org/details/performanceevalu0000unse/page/36">Performance Evaluation of Complex Systems: Techniques and Tools</a>. Lecture Notes in Computer Science. Vol. 2459. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/performanceevalu0000unse/page/36">36</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45798-4_3">10.1007/3-540-45798-4_3</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-44252-3</bdi>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFBolchGreinerde_MeerShridharbhai_Trivedi2006" class="citation book cs1">Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Shridharbhai Trivedi, Kishor (2006). Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2 ed.). John Wiley & Sons, Inc. p. 250. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0471565253</bdi>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFArtalejoGómez-Corral2008" class="citation book cs1">Artalejo, Jesús R.; Gómez-Corral, Antonio (2008). "The Matrix-Analytic Formalism". Retrial Queueing Systems. pp. 187–205. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-78725-9_7">10.1007/978-3-540-78725-9_7</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-78724-2</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFRiskaSmirni2002" class="citation journal cs1">Riska, A.; <a href="Evgenia_Smirni" title="Evgenia Smirni">Smirni, E.</a> (2002). "Exact aggregate solutions for M/G/1-type Markov processes". ACM SIGMETRICS Performance Evaluation Review. 30: 86. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.109.2225">10.1.1.109.2225</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F511399.511346">10.1145/511399.511346</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFRamaswami1988" class="citation journal cs1">Ramaswami, V. (1988). "A stable recursion for the steady state vector in markov chains of m/g/1 type". Communications in Statistics. Stochastic Models. 4: 183–188. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F15326348808807077">10.1080/15326348808807077</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFBiniLatoucheMeini2005" class="citation book cs1">Bini, D. A.; Latouche, G.; <a href="Beatrice_Meini" title="Beatrice Meini">Meini, B.</a> (2005). Numerical Methods for Structured Markov Chains. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Facprof%3Aoso%2F9780198527688.001.0001">10.1093/acprof:oso/9780198527688.001.0001</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780198527688</bdi>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFMeini1998" class="citation journal cs1"><a href="Beatrice_Meini" title="Beatrice Meini">Meini, B.</a> (1998). "Solving m/g/l type markov chains: Recent advances and applications". Communications in Statistics. Stochastic Models. 14 (1–2): 479–496. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F15326349808807483">10.1080/15326349808807483</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFRiskaSmirni2002" class="citation book cs1">Riska, A.; <a href="Evgenia_Smirni" title="Evgenia Smirni">Smirni, E.</a> (2002). "MAMSolver: A Matrix Analytic Methods Tool". Computer Performance Evaluation: Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2324. p. 205. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.2080">10.1.1.146.2080</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-46029-2_14">10.1007/3-540-46029-2_14</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-43539-6</bdi>.</cite>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Queueing_theory265" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Queueing_theory265" style="font-size:114%;margin:0 4em"><a href="Queueing_theory" title="Queueing theory">Queueing theory</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Single queueing nodes</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="D/M/1_queue" title="D/M/1 queue">D/M/1 queue</a></li>

<li><a href="M/D/1_queue" title="M/D/1 queue">M/D/1 queue</a></li>

<li><a href="M/D/c_queue" title="M/D/c queue">M/D/c queue</a></li>

<li><a href="M/M/1_queue" title="M/M/1 queue">M/M/1 queue</a>

<ul><li><a href="Burke's_theorem" title="Burke's theorem">Burke's theorem</a></li></ul></li>

<li><a href="M/M/c_queue" title="M/M/c queue">M/M/c queue</a></li>

<li><a href="M/M/%E2%88%9E_queue" title="M/M/∞ queue">M/M/∞ queue</a></li>

<li><a href="M/G/1_queue" title="M/G/1 queue">M/G/1 queue</a>

<ul><li><a href="Pollaczek%E2%80%93Khinchine_formula" title="Pollaczek–Khinchine formula">Pollaczek–Khinchine formula</a></li>

</ul></li>

<li><a href="M/G/k_queue" title="M/G/k queue">M/G/k queue</a></li>

<li><a href="G/M/1_queue" title="G/M/1 queue">G/M/1 queue</a></li>

<li><a href="G/G/1_queue" title="G/G/1 queue">G/G/1 queue</a>

<ul><li><a href="Kingman's_formula" title="Kingman's formula">Kingman's formula</a></li>

<li><a href="Lindley_equation" title="Lindley equation">Lindley equation</a></li></ul></li>

<li><a href="Fork%E2%80%93join_queue" title="Fork–join queue">Fork–join queue</a></li>

<li><a href="Bulk_queue" title="Bulk queue">Bulk queue</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Arrival processes</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Poisson_point_process" title="Poisson point process">Poisson point process</a></li>

<li><a href="Markovian_arrival_process" title="Markovian arrival process">Markovian arrival process</a></li>

<li><a href="Rational_arrival_process" title="Rational arrival process">Rational arrival process</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Queueing networks</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Jackson_network" title="Jackson network">Jackson network</a>

<ul><li><a href="Traffic_equations" title="Traffic equations">Traffic equations</a></li></ul></li>

<li><a href="Gordon%E2%80%93Newell_theorem" title="Gordon–Newell theorem">Gordon–Newell theorem</a>

<ul><li><a href="Mean_value_analysis" title="Mean value analysis">Mean value analysis</a></li>

<li><a href="Buzen's_algorithm" title="Buzen's algorithm">Buzen's algorithm</a></li></ul></li>

<li><a href="Kelly_network" title="Kelly network">Kelly network</a></li>

<li><a href="G-network" title="G-network">G-network</a></li>

<li><a href="BCMP_network" title="BCMP network">BCMP network</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Service policies</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Processor_sharing" title="Processor sharing">Processor sharing</a></li>

<li><a href="Round-robin_scheduling" title="Round-robin scheduling">Round-robin</a></li>

<li><a href="Shortest_job_next" title="Shortest job next">Shortest job next</a></li>

<li><a href="Shortest_remaining_time" title="Shortest remaining time">Shortest remaining time</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key concepts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Continuous-time_Markov_chain" title="Continuous-time Markov chain">Continuous-time Markov chain</a></li>

<li><a href="Kendall's_notation" title="Kendall's notation">Kendall's notation</a></li>

<li><a href="Little's_law" title="Little's law">Little's law</a></li>

<li><a href="Product-form_solution" title="Product-form solution">Product-form solution</a>

<ul><li><a href="Balance_equation" title="Balance equation">Balance equation</a></li>

<li><a href="Quasireversibility" title="Quasireversibility">Quasireversibility</a></li>

<li><a href="Flow-equivalent_server_method" title="Flow-equivalent server method">Flow-equivalent server method</a></li></ul></li>

<li><a href="Arrival_theorem" title="Arrival theorem">Arrival theorem</a></li>

<li><a href="Decomposition_method_(queueing_theory)" title="Decomposition method (queueing theory)">Decomposition method</a></li>

<li><a href="Bene%C5%A1_method" title="Beneš method">Beneš method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Limit theorems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fluid_limit" title="Fluid limit">Fluid limit</a></li>

<li><a href="Mean-field_theory" title="Mean-field theory">Mean-field theory</a></li>

<li><a href="Heavy_traffic_approximation" title="Heavy traffic approximation">Heavy traffic approximation</a>

<ul><li><a href="Reflected_Brownian_motion" title="Reflected Brownian motion">Reflected Brownian motion</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Extensions</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fluid_queue" title="Fluid queue">Fluid queue</a></li>

<li><a href="Layered_queueing_network" title="Layered queueing network">Layered queueing network</a></li>

<li><a href="Polling_system" title="Polling system">Polling system</a></li>

<li><a href="Adversarial_queueing_network" title="Adversarial queueing network">Adversarial queueing network</a></li>

<li><a href="Loss_network" title="Loss network">Loss network</a></li>

<li><a href="Retrial_queue" title="Retrial queue">Retrial queue</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Information_system" title="Information system">Information systems</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Data_buffer" title="Data buffer">Data buffer</a></li>

<li><a href="Erlang_(unit)" title="Erlang (unit)">Erlang (unit)</a></li>

<li><a href="Erlang_distribution" title="Erlang distribution">Erlang distribution</a></li>

<li><a href="Flow_control_(data)" title="Flow control (data)">Flow control (data)</a></li>

<li><a href="Message_queue" title="Message queue">Message queue</a></li>

<li><a href="Network_congestion" title="Network congestion">Network congestion</a></li>

<li><a href="Network_scheduler" title="Network scheduler">Network scheduler</a></li>

<li><a href="Pipeline_(software)" title="Pipeline (software)">Pipeline (software)</a></li>

<li><a href="Quality_of_service" title="Quality of service">Quality of service</a></li>

<li><a href="Scheduling_(computing)" title="Scheduling (computing)">Scheduling (computing)</a></li>

<li><a href="Teletraffic_engineering" title="Teletraffic engineering">Teletraffic engineering</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> Category</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-30" href="https://en.wikipedia.org/wiki/?title=Matrix_analytic_method&oldid=1283051879">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>